public class Solution {
    // 1.最大子数组和(贪心算法)
    public int maxSubArray(int[] nums) {
        //贪心法
        //遍历nums，若和小于0，则重新找子串(不重新找的话，拿得到的这个和为负数，就是个累赘)
        //max用来记录和的最大值
        int max = Integer.MIN_VALUE;
        int sum = 0;
        int len = nums.length;
        for(int i = 0; i < len; i++){
            sum += nums[i];
            max = Math.max(max, sum);
            if(sum < 0){
                sum = 0;
            }
        }
        return max;
    }
    //2.移动零(间接法，时间O(n))
    public void moveZeroes(int[] nums) {
        //间接法
        int len = nums.length;
        int[] tmpArr = new int[len];
        //临时数组下标
        int Index = 0;
        for(int i = 0; i < len; i++){
            if(nums[i] != 0){
                tmpArr[Index++] = nums[i];
            }
        }
        //直接覆盖nums
        for(int i = 0; i < len; i++){
            nums[i] = tmpArr[i];
        }
    }
    //2.移动零(双指针)
    public void moveZeroes(int[] nums) {
        //双指针
        int left = 0;
        int right = 0;
        int len = nums.length;
        while(right < len){
            //right找到非0数字就覆盖left
            if(nums[right] != 0){
                nums[left++] = nums[right];
            }
            right++;
        }
        //将后面的0补全
        while(left < len){
            nums[left++] = 0;
        }
    }
    //3.剑指 Offer 03. 数组中重复的数字(哈希法)
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(!set.contains(nums[i])){
                set.add(nums[i]);
            }else{
                return nums[i];
            }
        }
        return -1;
    }
    //4.二分查找
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    //5.多数元素(Map法)
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        //遍历一般记录出现个数
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i], 1);
            }else{
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            if(map.get(nums[i]) > len / 2){
                return nums[i];
            }
        }
        return -1;
    }
    //5.多数元素(排序法)
    public int majorityElement(int[] nums) {
        //先排序，然后数组中间元素就是多数元素
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
    //5.多数元素(摩尔投票法)
    public int majorityElement(int[] nums) {
        //摩尔投票法
        int key = nums[0];
        int count = 1;
        int len = nums.length;
        for(int i = 1; i < len; i++){
            if(key == nums[i]){
                count++;
            }else{
                count--;
            }
            if(count == 0){
                key = nums[i];
                count = 1;
            }
        }
        return key;
    }
    //5.多数元素 II
    public List<Integer> majorityElement(int[] nums) {
        //摩尔投票法
        List<Integer> list = new ArrayList<>();
        int len = nums.length;
        int key1 = nums[0];
        int key2 = nums[0];
        int count1 = 0;
        int count2 = 0;
        for(int i = 0; i < len; i++){
            if(nums[i] == key1){
                count1++;
                continue;
            }
            if(nums[i] == key2){
                count2++;
                continue;
            }
            if(count1 == 0){
                key1 = nums[i];
                count1++;
                continue;
            }
            if(count2 == 0){
                key2 = nums[i];
                count2++;
                continue;
            }
            count1--;
            count2--;
        }
        //到了这里，key1,key2若不为0，才可能是超过n/3的,这里要判断
        count1 = 0;
        count2 = 0;
        for(int i = 0; i < len; i++){
            if(nums[i] == key1){
                count1++;
            }else if(nums[i] == key2){
                count2++;
            }
        }
        if(count1 > len / 3){
            list.add(key1);
        }
        if(count2 > len / 3){
            list.add(key2);
        }
        return list;
    }
    //6.面试题 10.01. 合并排序的数组
    public void merge(int[] A, int m, int[] B, int n) {
        //数组tmpArr的下标
        int index = 0;
        int[] tmpArr = new int[n + m];
        int a = 0;
        int b = 0;
        while(b < n && a < m){
            if(A[a] > B[b]){
                tmpArr[index++] = B[b++];
            }else{
                tmpArr[index++] = A[a++];
            }
        }
        //将没比较完的放入
        while(b < n){
            tmpArr[index++] = B[b++];
        }
        while(a < m){
            tmpArr[index++] = A[a++];
        }
        //覆盖
        for(int i = 0; i < m + n; i++){
            A[i] = tmpArr[i];
        }
    }
    //7.跳跃游戏
    public boolean canJump(int[] nums) {
        //贪心算法
        //保存能跳到的最远的下标
        int len = nums.length;
        int max = 0;
        for(int i = 0; i < len; i++){
            //首先要能跳到下一个位置
            if(max >= i){
                //更新能跳到的最远位置
                max = Math.max(nums[i] + i, max);
                if(max >= len - 1){
                    return true;
                }
            }
        }
        return false;
    }
    //8.打家劫舍
    public int rob(int[] nums) {
        //动态规划
        //f(0) = 0;没房子，就没得偷
        //f(1) = nums[0];就一间房子，只能偷这一间
        //f(k) = max{f(k - 1), max{f(0),f(1)...f(k - 2)} + nums[k - 1]}得出以下式子
        //f(k - 2) >= f(k - 3)是因为f(k)表示能在前K个里面偷到的最大值
        //f(k) = max{f(k - 1), f(k - 2) + nums[k - 1]};
        //f(k - 1)表示不偷最后一间，f(k - 2 + nums[k - 1])表示偷最后一间，不偷倒数第二间
        int k = nums.length;
        int[] array = new int[k + 1];
        array[0] = 0;
        array[1] = nums[0];
        for(int i = 2; i <= k; i++){
            array[i] = Math.max(array[i - 1], array[i - 2] + nums[i - 1]);
        }
        return array[k];
    }
    //9.搜索旋转排序数组(二分法升级)
    public int search(int[] nums, int target) {
        //二分法，以区域进行二分，中间值小于最右边，说明最右边有序，左边同理
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){//找到了
                return mid;
            }else if(nums[mid] < nums[right]){//右边有序
                //注意，虽然有序了，但是并不能说明目标就在这边
                //但是是有序的，就可以判断以下目标是否在这个范围
                if(nums[mid] < target && target <= nums[right]){
                    left = mid + 1;
                }else{//不在这个区域，就向另一个范围缩小
                    right = mid - 1;
                }
            }else{//左边有序
                if(nums[left] <= target && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }

        }
        return -1;
    }
    //10.买卖股票的最佳时机 II
    public int maxProfit(int[] prices) {
        //只要赚钱(后一个比前一个大)就卖，最后利益肯定最大
        int profit = 0;
        for(int i = 0; i < prices.length - 1; i++){
            if(prices[i + 1] > prices[i]){
                profit += prices[i + 1] - prices[i];
            }
        }
        return profit;
    }
}
